#define _CRT_SECURE_NO_WARNINGS 1
//#include <iostream>
//#include <thread>
//#include <mutex>

//std::mutex _mtx;
//
//void print(int k, int n)
//{
//	_mtx.lock();
//	for (int i = k; i <= n; i++)
//	{
//		std::cout << i << " ";
//	}
//	_mtx.unlock();
//
//	std::cout << std::endl;
//}

//int main()
//{
//	std::thread t1(print, 5, 20);
//	std::thread t2(print, 25, 40);
//
//	std::cout << t1.get_id() << std::endl;
//	std::cout << t2.get_id() << std::endl;
//
//	t1.join();
//	t2.join();
//
//	std::cout << std::this_thread::get_id << std::endl;
//
//	return 0;
//}

//int main()
//{
//	std::mutex _mtx;
//
//	std::thread t1([&]
//		{
//			_mtx.lock();
//			for (int i = 1; i <= 100; i++)
//			{
//				std::cout << i << " ";
//			}
//			std::cout << std::endl;
//			_mtx.unlock();
//		});
//	
//	std::thread t2([&]
//		{
//			_mtx.lock();
//			for (int i = 1; i <= 100; i++)
//			{
//				std::cout << i << " ";
//			}
//			_mtx.unlock();
//		});
//
//	t1.join();
//	t2.join();
//
//	return 0;
//}

//int main()
//{
//	std::mutex mtx;
//	bool flag = true;
//	std::condition_variable c;
//	int n = 100;
//
//	std::thread t1(
//		[&] 
//		{
//			int i = 0;
//			while (i < n)
//			{
//				std::unique_lock<std::mutex> lock(_mtx);
//
//				while (!flag)
//				{
//					c.wait(lock);
//				}
//
//				std::cout << i << " ";
//				i += 2;
//				flag = false;
//
//				c.notify_one();
//			}
//			
//		}
//	);
//
//	std::thread t2
//	(
//		[&]
//		{
//			int j = 1;
//			while (j < n)
//			{
//				std::unique_lock<std::mutex> lock(mtx);
//
//				while (flag)
//				{
//					c.wait(lock);
//				}
//
//				std::cout << j << " ";
//				j += 2;
//				flag = true;
//
//				c.notify_one();
//			}
//		}
//	);
//
//	t1.join();
//	t2.join();
//
//
//	return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//
//struct ListNode
//{
//    int val;
//    ListNode* next;
//    ListNode() : val(0), next(nullptr) {}
//    ListNode(int x) : val(x), next(nullptr) {}
//    ListNode(int x, ListNode* next) : val(x), next(next) {}
//};
//class Solution {
//public:
//    ListNode* reverseBetween(ListNode* head, int left, int right) 
//    {
//        if (left == right) return head;
//
//        ListNode* dummy = new ListNode(0);
//        dummy->next = head;
//        ListNode* pre = dummy;
//        for (int i = 1; i < left; i++) 
//            pre = pre->next;
//        ListNode* cur = pre->next;
//        ListNode* next = nullptr;
//        for (int i = left; i < right; i++) 
//        {
//            next = cur->next;
//            cur->next = next->next;
//            next->next = pre->next;
//            pre->next = next;
//        }
//        return dummy->next;
//    }
//};
//ListNode* createList(vector<int> values) 
//{
//    if (values.empty()) return nullptr;
//    ListNode* head = new ListNode(values[0]);
//    ListNode* current = head;
//    for (int i = 1; i < values.size(); i++) 
//    {
//        current->next = new ListNode(values[i]);
//        current = current->next;
//    }
//    return head;
//}
//void printList(ListNode* head) 
//{
//    while (head) 
//    {
//        cout << head->val;
//        if (head->next) cout << "->";
//        head = head->next;
//    }
//    cout << endl;
//}
//
//int main()
//{
//    Solution solution;
//
//    ListNode* head1 = createList({ 1, 2, 3, 4, 5 });
//    ListNode* result1 = solution.reverseBetween(head1, 2, 4);
//    printList(result1); 
//
//    ListNode* head2 = createList({ 5 });
//    ListNode* result2 = solution.reverseBetween(head2, 1, 1);
//    printList(result2); 
//
//    return 0;
//}
//
//#include <iostream>
//using namespace std;
//
//void bubbleSort(int arr[], int n) 
//{
//    for (int i = 0; i < n - 1; i++) 
//    {
//        for (int j = 0; j < n - i - 1; j++) 
//        {
//            if (arr[j] > arr[j + 1]) 
//            {
//                int temp = arr[j];
//                arr[j] = arr[j + 1];
//                arr[j + 1] = temp;
//            }
//        }
//    }
//}
//
//void printArray(int arr[], int n) 
//{
//    for (int i = 0; i < n; i++) 
//        cout << arr[i] << " ";
//    cout << endl;
//}
//
//int main() {
//    int arr[10];
//    for (int i = 0; i < 10; i++) cin >> arr[i];
//    bubbleSort(arr, 10);
//
//    printArray(arr, 10);
//    return 0;
//}
//
//#include <stdio.h>
//
//int Fib(int n) 
//{
//    if (n <= 2) return 1;
//    return Fib(n - 1) + Fib(n - 2);
//}
//
//int main() {
//    int n;
//    scanf("%d", &n);
//
//    printf("%d\n", n, Fib(n));
//    return 0;
//}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if (prices.empty()) return 0;

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.size(); i++) 
        {
            if (prices[i] < minPrice) minPrice = prices[i];
            else if (prices[i] - minPrice > maxProfit) maxProfit = prices[i] - minPrice;
        }
        return maxProfit;
    }
};


int main() 
{
    Solution solution;

    vector<int> prices1 = { 7, 1, 5, 3, 6, 4 };
    cout << solution.maxProfit(prices1) << endl;

    vector<int> prices2 = { 7, 6, 4, 3, 1 };
    cout << solution.maxProfit(prices2) << endl;
    return 0;
}